The field of wireless communications has seen dramatic growth recently. Cellular telephones and pagers are devices commonly owned and used by a wide cross section of the population. Further, devices such as portable personal computers, personal data assistants (PDAs), and the like are becoming more common in the general population of users and have begun to be used in wireless networks.
In an ad hoc wireless network these devices communicate directly with one another and/or are routed through a number of devices to communicate with their ultimate destination. For example, referring now to FIG. 1, a plurality of users 100–118 are dispersed within a given area, and each user 100–118 has a wireless device equipped to communicate with the wireless devices of the other users 100–118. The user 100 may wish to communicate with the user 104. One path or route through which the communications may occur is through the intermediate users 108, 106. That is, the user 100 broadcasts a signal directed to the user 104. The user 108 receives the signal, recognizes that it is directed to the user 104, and passes the signal along. Likewise, the user 106 receives the signal, recognizes that it is directed to the user 104, and passes the signal along to the user 104. Thus, the user 104 ultimately receives the signal.
In a system of this type, each user keeps track of the other users with which it can communicate. As it is an ad hoc network with many users moving relatively randomly, it is inevitable and desirable that users will routinely enter and leave a local area. Thus, each user must periodically update its list of users with whom it can communicate. The process of keeping track of all of the other users with whom a user may communicate can consume substantial processing resources of the wireless device. That is, the wireless device may be unable, or at least inefficient at, keeping up-to-date information on all users with which it may communicate.
Accordingly, it has been suggested that a user A keep track of only those routes to other users that are most likely to be used. The selected users are referred to as being in a pro-active region of the user A relative to the other users, and the remaining users in the area are identified as being in a reactive region. In one suggested system, the wireless device identifies the users in its proactive region by selecting only those other wireless devices that are within two “hops.” That is, if a user can reach another user, but it requires that the communication be forwarded by more than two intermediate devices, then the user is designated to be in the reactive region. Such a system is attractive because of its simplicity, but it will often result in inferior, or at least suboptimal, pro-active regions.
A two hop pro-active region does not take into account a number of significant factors. For example, while the pro active radius may be set to only two hops, geographic features, such as mountains, may exclude other desired users from the pro active region. Likewise, the two hop pro-active region may include a user that is currently only one hop distant, but may be moving quickly in a direction to take the user entirely outside the pro active region, or at least beyond the two hop limit. Determining which devices fall within the pro-active region, as opposed to the reactive region has proven problematic.
The present invention is directed to overcoming, or at least reducing the effects of, one or more of the problems set forth above.
While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof have been shown by way of example in the drawings and are herein described in detail. It should be understood, however, that the description herein of specific embodiments not intended to limit the invention to the particular forms disclosed, but on the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention as defined by the appended claims.